import java.util.LinkedList;
import java.util.Queue;

public class Solution1631 {

    int[] dx={0,1,0,-1};
    int[] dy={1,0,-1,0};

    public int minimumEffortPath(int[][] heights) {
        int l=0,r=1,ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (check(mid,heights)){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }

    private boolean check(int t,int[][] heights) {
        Queue<int[]> queue=new LinkedList<>();
        int[][] visit=new int[heights.length][heights[0].length];
        visit[0][0]=1;
        queue.offer(new int[]{0,0});
        while (!queue.isEmpty()){
            int[] p=queue.poll();
            for (int i = 0; i < 4; i++) {
                int x=p[0]+dx[i];
                int y=p[1]+dy[i];
                if (valid(x,y,heights.length,heights[0].length) && visit[x][y]==0 && Math.abs(heights[x][y]-heights[p[0]][p[1]])<=t){
                    queue.offer(new int[]{x,y});
                    visit[x][y]=1;
                }
            }
        }
        return visit[heights.length-1][heights[0].length-1]==1;
    }

    private boolean valid(int x, int y, int l1, int l2) {
        return x>=0 && x<l1 && y>=0 && y<l2;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1631().minimumEffortPath(new int[][]{{1,2,3,4,5,6}}));
    }
}
